package mess;

import java.util.Arrays;

public class LeeCode_41 {
    public static void main(String[] args) {
        System.out.println(firstMissingPositive2(new int[]{1}));
    }

    private static int firstMissingPositive(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        int index = 1;
        for(int i = 0; i < len; i++){
            if(nums[i] > 0){
                if(nums[i] != index)
                    return index;
                if(i < len - 1 && nums[i] != nums[i + 1])
                    index++;
            }
        }
        return nums[len - 1] > 0 ? nums[len - 1] + 1: 1;
    }

    private static int firstMissingPositive2(int[] nums) {
        int len = nums.length;
        int[] arr = new int[len];
        for (int num : nums) {
            if (num > 0 && num <= len) {
                arr[num - 1] = num;
            }
        }
        for (int i = 1; i <= len; i++) {
            if (arr[i - 1] != i)
                return i;
        }
        return len + 1;
    }
}
